COMMENT ⊗   VALID 00007 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	January l, l959
C00006 00003	This time is substantially reduced by the use of better programming
C00010 00004	of a programmer reading his dump.  He looks at where the program stopped.
C00014 00005	     The only way quick response can be provided at a bearable
C00018 00006	     3.  Preventing a bad program from destroying other programs.
C00021 00007	            	                                    
C00024 ENDMK
C⊗;
January l, l959





To:        Professor P.M. Morse
From:      John McCarthy
Subject:   A Time Sharing Operator Program for our Projected IBM 709

l.  INTRODUCTION

    This memorandum is based on the assumption that MIT will be
given a transistorized IBM 700∩↓CE←kPA∃kYdAXrl@\@A∩↓oC]h↓i↑AaI←a←g∀~∃C\↓←aKe¬iS]N↓gsgi∃ZAM←HAShAQQChA]SYXAMkEgi¬]iSC1YrAe∃IkGJ↓iQJAQS[J~)eKck%eKHAQ↑AOKPABAaI←EYK4Ag←YYKHA←8AiQJ↓[CGQ%]J\@↓β]rA≥kKgf↓CfAi<@~∃Q=nA[k
PA←L↓BAeK⊃kGiS=\Ao←UYHAE∀ACGQ%KmKH↓SfAUUghAB↓OkKgLXAEkPAB@~)MCGi=dA←L↓MSmJ↓gKK[LAG←]MKemCQSmJ\AαAg5CYYKHAMCGQ←dA←_AS[aI←mK[∃]h~∃%\AiQ∀AC[←U]hA←_A[CG!S]JAQS[JAUgKHA]←kYH↓CYg↑↓EJAC
QSKm∃H\~∀4∀@@@A)QJ↓ae←a=gCXAIKckSIKfAB↓G←[a1KiJAIKmSg%←\AS8AiQJ↓oCrAQQJA[¬GQS]∀~∃Sf↓kgKH0AoSY0AeKcUSeJA∧AY←]≤AaKe%←HA←_AaeKACeCi%←\XAQQJAI∃mKY←A[K]h4∃←LAM←[JA9KnAKEkSa[∃]hXA¬]HAB↓OeKCPAIKC0A←LA
←←aKICiS←8AC]H↓KmK\4∃G←Y1CE←e¬iS←\↓Me←Z↓∪¬~\A)QKIKM←e∀XASL↓iQJAAe←a←MCXASLAi↑A	JAG←8Z~∃g%IKeK⊂AgKe%←kgYdXASh↓gQ←k1HAEJ↓G←]g%IKeK⊂AS[[∃ISCi∃Yr\@↓∩AiQ%]V@~)iQJAAe←a←MCXAa=S]if↓i↑Ai!JAoCdACYX↓G←[aUiKef↓oSYX↓EJA←AKeCi∃HAS\~∃iQ∀AMkiUeJXA¬]HAo∀AQCm∀ABAG!C]GJ↓i↑Aa%←]KKHABAE%NAgi∃`AM←IoCeH↓S\~∃QQJAo¬rAG←5akiKIfACe∀AkgK⊂\@A)!JASI∃CfAKaaeKgMKHAS8AiQJ↓M←YY=oS]N4∃gKGQS←]f↓CeJA9←hAKMaKGS¬YYrA9KnXA	khAi!KrAQ¬mJAM=e[Ke1rAEK∃\AG←8Z~∃g%IKeK⊂AS[aICGiS
CXAo%iPAi!JAG←5akiKIfAae∃mS←kMYrACYCSYC	YJ\@↓)QKr~∃Ce∀A]←h↓KCgr↓M←dA
←[akQKdAI∃gSO]∃efAi<AIKm∃Y←`A%]IKa∃]IK]QYrAg%]GJ~)iQKr↓S]m←1mJAaI←OeC5[S]N↓gsgi∃ZAIKMSO\A5kGPA5←eJAQQC\A5CGQS9JAIKMSO\\4∀~∀d8@AαAE+∪π⊗↓'%-%π
Aπ=≠!+)∃$~∀~(@@@A
←[akQKefA]KeJA=eSOS9CYYr↓IKmK1←aKH↓oSiP↓iQJA%IKBAQQCh~)ae←OIC[fA]←kYH↓EJAoISiiK8Ai↑AM←YmJ↓OK]KICXAG1CggKLA←LAAe←EY∃[fAC9H~∃i!ChAC→iKdA¬\AS]%iSCX↓aKeS=HA[←MhA←L↓iQJA
←[akQKdAi%[JAo=kYHA	J~∃gAK]hA%\Aek9]S]N↓iQKg∀AgiC9ICeH↓ae←OIC[fA]SiPA9KnAg∃ifA←_AICi∧\~∃)!SfAm%KnAG=[aYKQKYrAU]IKe∃giS[¬iKHAQQJAm¬eSKidA←LAUgKfAQ↑AoQ%GP@~)G←[aUiKef↓o←kY⊂AEJAAkh\@↓)QJA¬GikC0AgSiUCiS←8ASfA5kGPA
Y←gKHAi↑AQQJ~∃=aa←g%iJAKaieK[∀XAoQ∃eKS\↓KCGP↓kgKd↓←LAi!JA[C
QS]J↓QCfAQ↑Aoe%iJ~∃!SfA←]\Aae=OeCZ↓C]HAQQChA=]GJAQQSfAAe←Oe¬ZASf↓IKEk≥OKHX↓←]JAIk\~∃M←YmKLAiQJ↓ae←E1KZ\@↓)QSf↓[KC]LAiQCPAiQJ↓iS[J↓eKck%eKHAQ↑Ag←1mJ@~)iQJAAe←EY∃ZAG←9gSgiLA[CS9YrA←_AiS[∀AeKcUSeKH↓i↑AI∃EkNAQQJAaI←OeC4\@@~(→)QSLAiS[∀ASfAMkEgi¬]iSC1YrAe∃IkGK⊂AErAQQJAkMJA←L↓EKii∃dAae=OeC[5S]N~)YC]OUCOKf↓gkGP↓CfA
=eieC8XA→∪M @Qi!JAYC9OkCO∀AiQJ↓βeiS→SGSC0~∃∪]QKYYS≥K]GJ↓∂e←k@ASfA⊃KmKY=aS]N↓M←dAMs[E←1SFA[¬]Sak1CiS←9fRAC9H~∃π=≠∪(@!3]Om∀OfAY¬]OkC≥JR\@↓⊃←oKYKdXA∧AMkeQQKdA1CeOJ↓eKIk
iS←\↓GC\~)EJAC
QSKm∃HAEr↓eKIk
S]NAQQJAe∃ga←]MJAiS5JA←L↓iQJA
←[akQCiS←8AGK]QKd\~(~∀@@@A)Q∀AeKgA←]gJ↓iS[J↓←LAi!JA≠∪PAπ←[AkiCi%←\Aπ∃]iKd↓i↑AB↓aKeM=e[C]
J~∃e∃ckKgPAaeKMK]iYdAmCe%KfAMI←Z@f↓Q←keLAi↑@LlAQ←UefAI∃aK]I%]NA←8AiQJ4∃giCQJA←L↓iQJA5CGQS9JXAi!JAKM→SGSK9GrA←_AiQJ↓←aKe¬i←dX↓C]HAQQJ~∃	CGWY=NA←L↓o←eV8@A/J↓ae←a=gJAEdAiS[∀AgQCIS]NX↓i↑Ae∃IkGJ↓iQSf4∃eKgA←]gJ↓iS[J↓i↑Ai!JA←e⊃KdA←_@bAg∃G←]H↓M←dA
KeiC%\AakIa←gKL\@A→∃h~∃kLAMSeMhAG←9gSIKHAQ←n↓iQJAAe←a←MKHAgegiKZ↓Y←←WLAi↑AQQJAkMKdAE∃M←eJ4∃oJA
←]gS⊃KdAQ=nASh↓SfAi<AEJA¬GQSKYKH\~(~∀@@@A'kAa←gJ↓iQJA¬mKeC≥JAae=OeCZ↓i↑AE∀AIKEUOOKH↓G←]g%gifA=L@j`@~∃S]MiekGQS←]f↓aYkf↓giC]⊃CeHAMkEe←UiS]KLAC]H↓iQCh↓iQJAQS[JAIKckSIKH~∃U]IKd↓iQJAAeKgK9hAgsMiKZA→←dAC8ACmKICOJA⊃KEkO≥S]NAIk\ASL@fA[%]kiKL\~∃)!SfASLAiS[∀AK]←UOPAi<AKqK
kiJ@\X```0```@\`hAS9giek
iS←]LA←dAQ↑~∃KaKGki∀AKCG AS]gQekGi%←\AS8AiQJ↓ae←OICZAXPX```↓iS[KL\~∀~(@@@@↓≠←gh↓←LAi!JAKeI←efA%\Aae=OeC[LAG←k1HAEJ↓M←k]⊂AErAMS]OY∀Z~∃gQKaaS9NA←d↓[kYi%aYJ[MiKaa%]NAi!JAae=OeCZ↓CfAkMKHAi<AEJA⊃←]J\4∃∪LAQQJAaI←OeC4ASfA⊃KEkO≥KHAS8AiQSLAoCr0AiQJ↓ae←OICZAo%YXAkMkCYYd~∃Kq∃GkiJ↓KCGP↓S]giIkGiS=\A]←PA[←e∀AiQC8@b`AQS[Kf0@b↑bP``ACLA[C]d~∃Kq∃GkiS=]fACLAChAAeKgK9h\@A=LAG←UegJX↓EKGCUgJA←_AgY←\AQk[¬\AeJ4~∃CGQS←]f↓iQJA=YHAgegiKZ↓oCfA∃mK\A5←eJA]CgiK→kXA←_AG←[AkiKd↓iS[J4∃iQC8AiQJ↓aeKg∃]hA←9J\@A]QKeJ0AQ←o∃mKdX↓I←Kf↓CYXAQQJAG=[aki∃dAiS5J~∃O<}~∀~(@@@@↓βhAaIKgK]PA[←gPA←LAQQJAG=[aki∃dAiS5JASf↓gaK]PAS\A
←]mKIgS←\4∀Q'β@[ES]¬erXA⊃KGS[¬X[ES9CerX↓ES]CIr[IK
S[CX0AES]¬er[←
iCXR↓C]HA%\~∃oISiS]≤AiCa∀AC]H↓eKCI%]NAi¬aJAC9HAGCIIf\~(~∀@@@A/QdASfAM↑A[k
PAiS5JAga∃]hAS8AG←]YKegS=\AC]⊂AS]aUhA←kQakh\4∀~∀@@@@@b\@A∃mKer↓ieSC0Aek\↓eKck%eKfA∧AMeKMPAgKPA←LA
←]mKIgS←]L\~∀@@@@@@~∀@@@@@d\@A	KGCkMJA←L↓iQJAMY←nAIKga←9gJAi%[JA←_AiQJ↓gsgi∃ZASh↓Sf~∃9KGKgMCerAQ↑AiC-JAYCIOJAIU[afA→←dAM∃CdA←_A]←h↓EKS]≤ACEY∀Ai↑A→S]H~)iQJA∃ee←d8@A)Q∀AYCe≥JAIk5afACIJA[C%]YrAU]eKC⊂XAEkPA]Km∃eiQK1KgfX4∃iQKdACeJ↓]KGKMgCer8@A)↑↓gKJA]QrAi!SfASLAg↑X↓G←]g%IKdAQQJAE∃QCmS=d~∀→←LA∧Aae←≥eC[[∃dAeK¬IS]N↓QSfA⊃k[`\A⊃JA1←←Wf↓ChAo!KeJAQQJAaI←OeC4Agi←AaKH\4∃)QK8AQJA1←←Wf↓ChAi!JAeK≥SgiKIfAG←9iCS]%]NAi!JAaCIiSCX↓eKgk1ifAg<AMCd4∃G←[AkiKH8@A)Q%fAgk≥OKgiLAY←←-S]NA¬hABA
KeiC%\Aa←%]hAS8AiQJ↓ae←OICZ\@↓)QJ~)ae←OIC[[KHA[Cr↓MS]H↓QSfA5SgiC-JACMQKdAY=←WS]≤AChA9←hA[=eJAi!C\@d@~∃eK≥SgiKIfA←kPA←LAMCr@b@``AIU[aKH0AEkh↓i↑AQ¬mJAaIKISGQKHAo!SGP@H`Ao←UYH~∃!CmJA	KK\A%[a←gMSEYJ↓S\AC⊃mC]G∀AC]H↓i↑AQ¬mJAe∃IkGK⊂AiQJb```4∃gkEMiC]i%CYYr↓o←kY⊂AQCm∀AeKcUSeKH↓GYKm∃e]KgLACfAMkEUK
hAi↑↓Kee←HACf@↓QSf~)ae←OICZ\@↓)QJAAe←Oe¬[[Kd↓G←kY⊂AQCm∀AiCW∃\ABAIk\Ai get the first register
looked at, then another run for the second, etc., but this would have
required 60 hours at least of elapsed time to find the bug according to
our assumptions and a large amount of computer time for repeated loading 
and re-runnings.  The response time of the sheet paper containing the dump 
for any register is only a few seconds which is OK except that one dump
does not usually contain information enough to get the entire program
correct.

     Suppose that the programmer has a keyboard at the computer
and is equipped with a substantial improvement on the TXO interro-
gation and intervention program (UT3).  (The improvements are in
the direction of expressing input and output in a good programming
language.)  Then he can try his program, interrogate individual pieces
of data or program to find an error, make a change in the source
language and try again.

     If he can write program in source language directly into the
computer and have it checked as he writes it, he can save additional
time.  The ability to check out a program immediately after writing
it saves still more time by using the fresh memory of the programmer.
I think a factor of 5 can be gained in the speed of getting pro-
grams written and working over present practice if the above-
mentioned facilities are provided.  There is another way of using
these facilities which was discussed by S. Ulam a couple of years
ago.  This is to use the computer for trial and error procedures
where the error correction is performed by a human adjusting 
parameter.

     The only way quick response can be provided at a bearable
cost is by time-sharing.  That is, the computer must attend to 
other customers while one customer is reacting to some output.

3.  THE PROBLEM OF A TIME-SHARING OPERATOR SYSTEM

     I have not seen any comprehensive written treatment of the
time-sharing problem and have not discussed the problem with
anyone who had a complete idea of the problem.  This treatment is 
certainly incomplete and is somewhat off the cuff.  The
equipment required for time-sharing is the following:

     a.  Interrogation and display devices (flexowriters are possible
but there may be better and cheaper).
     b.  An interrupt feature on the computer -- we'll have it.
     c.  An exchange to mediate between the computer and the
external devices.  This is the most substantial engineering problem, 
but IBM may have solved it.

     In general the equipment required for time-sharing is well
understood, is being developed for various advanced computers, e.g., 
Stretch TX2, Metrovich 1010, Edsac 3.  I would not be surprised if
almost all of it is available with the transistorized 709.  However,
the time-sharing has been worked out mainly in connection with
real-time devices.  The programs sharing the computer during any 
run are assumed to occupy prescribed areas of storage, to be
debugged already, and to have been written together as a system.
We shall have to deal with a continuously changing population of
programs, most of which are erroneous.

     The major problems connected with time-sharing during pro-
gram development seem to be as follows:

     l.  Allocating memory automatically between the programs.
This requires that programs be assembled in a relocatable form 
and have a preface that enables the operator program to organize the
program, its data, and its use of common subroutines.

     2.  Recovery from stops and loops.  The best solutions to these
problems require 

         a.  Changing the stop instructions to trap instructions.
     This is a minor modification to the machine.  (At least it will
     be minor for the 704.)
         b.  Providing a real time alarm clock as an external device.

     3.  Preventing a bad program from destroying other programs.
This could be solved fairly readily with a memory range trap which
might not be a feasible modification.  Without it, there are pro-
gramming solutions which are less satisfactory but should be good
enough.  These include:

     l.  Translations can be written so that the programs
they produce cannot get outside their assigned storage areas.  A
very minor modification would do this to Fortran.

     2.  Checksums can be used for machine language programs.

     3.  Programming techniques can be encouraged which make destruction
of other programs unlikely.

     4.  There is an excessive tendency to worry about this
point.  The risk can be brought down to the present risk of having
a program ruined by operator or machine error.

4.  SUMMARY

     l.  We may be able to make a major advance in the art of
using a computer by adopting a time-sharing operator program for
our hoped-for 709.

     2.  Such a system will require a lot of advance preparation
starting right away.

     3.  Experiments with using the flexo connection to the
real-time package on the 704 will help but we cannot wait for the
results if we want a time-sharing operator program in July l960.

     4.  The cooperation of IBM is very important but it should 
be to their advantage to develop this new way of using a computer.

     5.  I think other people at MIT than the Computation Center 
staff can be interested in the systems and other engineering
problems involved.







            	                                    

OXFORD UNIVERSITY COMPUTING LABORATORY                45 Banbury Road

PROGRAMMING RESEARCH GROUP                            Oxford   OX2 6PE


                                                      1st May 1974



Professor D. E. Knuth
Stanford University
Computer Science Department
Stanford, California  94305
U.S.A.

Dear Don:

     The paper I wrote called `Time Sharing in Large Fast
Computers' was read at the first (pre IFIP) conference at
Paris in l960.  It was mainly about multi--programming (to
avoid waiting for peripherals) although it did envisage this
going on at the same time as a programmer was debugging his program
at a console.  I did not envisage the sort of console system which
is now so confusingly called time sharing.  I still think my use
of the term is the more natural.

     I am afraid I am so rushed at the moment, being virtually
alone in the PRG and having just moved house, that I have no
time to look up any old notes I may have.  I hope to be able to
do so while settling in and if I find anything of interest I
will let you know.

     Don't place too much reliance on Halsbury's accuracy.  He
tends to rely on memory and get the details wrong.  But he was
certainly right to say that in l960 `time sharing' as a phrase 
was much in the air.  It was, however, generally used in my sense
rather than in John McCarthy's sense of a CTSS-like object.

     Best wishes,

                              Yours sincerely,

                              C. Strachey
                              Professor of Computation
                              University of Oxford